package 力扣.排序.合并排序;

import java.util.Arrays;

public class 模板 {
    public static void main(String[] args) {
        int[] nums = {3,4,5,2,5,6,2,65,123,0};
        mergeSort2(nums);
        System.out.println(Arrays.toString(nums));
    }

    /**
     边中递合拷（4参）
     */
    private static void mergeSort(int[] nums){
        if (nums == null ||nums.length ==0){
            return;
        }
        int[] t = new int[nums.length];//临时中专数组
        msort(nums,0,nums.length,t);
    }

    private static void msort(int[] nums, int b, int e, int[] t) {
        if (b >= e || b + 1 >= e){//边界
            return;
        }
        //拆分
        int mid = b + ((e - b) >> 1);
        msort(nums, b, mid, t);
        msort(nums, mid, e, t);
        //合并
        int i = b;
        int j = mid;
        int to = b;
        while (i < mid || j < e){
            if (j >= e || (i < mid && nums[i] <= nums[j])){
                t[to++] = nums[i++];
            }else{
                t[to++] = nums[j++];
            }
        }
        //拷贝
        for (int k = b; k < e; k++) {
            nums[k] = t[k];
        }

    }

    private static void mergeSort2(int[] nums){
        if (nums == null || nums.length == 0){
            return;
        }
        //设置拷贝数组
        final int N = nums.length;
        int[] ints = new int[N];
//        msort2(nums,0,N,ints);
        mergeSort(nums,0,N,ints);
    }

    private static void msort2(int[] nums, int b, int e, int[] ints) {
        if (b + 1 >= e){//最多一个元素，不用合并
            return;
        }
        int m = b + ((e - b) >> 1);
        msort2(nums, b, m, ints);
        msort2(nums, m, e, ints);
        //合并
        int i = b;
        int j = m;
        int pos = b;
        while (i < m || j <e){
            if (j >= e || i < m && nums[i] < nums[j]){
                ints[pos++] = nums[i++];
            }else {
                ints[pos++] = nums[j++];
            }
        }
        //拷贝
        System.arraycopy(ints, b, nums, b, e - b);
    }

    /**
     * 合并排序核心代码
     * @param nums 原数组
     * @param b   左边界
     * @param e   右边界
     * @param ints 临时拷贝数组
     */
    private static void mergeSort(int[] nums, int b , int e , int[] ints){
        if (b + 1 >= e){
            return;
        }
        int m = b + (e - b >> 1);
        mergeSort(nums, b, m, ints);
        mergeSort(nums, m, e, ints);

        int i = b;
        int j = m;
        int p = 0;
        //两路合并
        while (i < m || j < e){
            if (j >= e ||  i < m && nums[i] <= nums[j]){ //不要漏写 i < m
                ints[p++] = nums[i++];
            }else{
                ints[p++] = nums[j++];
            }
        }
        System.arraycopy(ints , 0 , nums , b , e - b);
    }
}
